// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

// 进阶：你能尝试使用一趟扫描实现吗？

// 执行用时：
// 0 ms
// , 在所有 C++ 提交中击败了
// 100.00%
// 的用户
// 内存消耗：
// 10.4 MB
// , 在所有 C++ 提交中击败了
// 57.18%
// 的用户

// 两遍扫描


#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<set>
using namespace std;


 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int before_n=0;
        ListNode* cur = head;
        while(cur !=NULL){
            cur = cur->next;
            before_n++;
        }
        cur = head;
        if(before_n<0){
            return NULL;
        }
        before_n = before_n-n-1;
        if(before_n == -1){
            return head->next;
        }
        while(head !=NULL){
            if(before_n==0){
                head->next = head->next->next;
                // before_n--;
                break;
            }
            else{
                head = head->next;
                before_n--;
            }
        }
        return cur;
    }
};